// 给定一个二叉树，返回所有从根节点到叶子节点的路径。
// 说明: 叶子节点是指没有子节点的节点。

function binaryTreePaths(root: TreeNode | null): string[] {
    if (!root) {// 安全校验
        return [];
    }
    const res: string[] = []; // 结果数组
    binaryTreePaths_DFS(root, res, []);
    return res;
};

function binaryTreePaths_DFS(root: TreeNode, res: string[], path: number[]) {
    path.push(root.val);// 将当前节点值加入路径
    if (!root.left && !root.right) { // 递归出口
        res.push(Array.from(path).join('->'));
        path.pop();// 回溯
        return;
    }
    if (root.left) {
        binaryTreePaths_DFS(root.left, res, path);
    }
    if (root.right) {
        binaryTreePaths_DFS(root.right, res, path);
    }
    path.pop();// 当前节点的左右子树已经深度优先搜索完毕，撤销回退
}

// 这道题目乍看觉得难度并不大，但是如果需要把每个细节写对的话还是有一些难度的。
// 首先确定是一个用深度优先搜索可解的题目，我们用路径数组来记录走过的路径
// 思考递归的终点，其实正确的应该是若当前节点的左右子树为空的情况下
// 说明这条路径已经走到头了，是结果，我们将它用箭头拼接成字符串加入结果数组
// 这里注意第一个点，那就是加入结果数组后记得撤销最后一个路径元素，做状态重置
// 之后在每一轮递归中，我们应该把当前的节点值加入路径数组中
// 然后判断当前节点的左右子树是否存在，若存在我们就对它的左右子树继续深搜
// 这里要注意的第二个点：若当前节点的左右节点都已经进行过深度优先搜索
// 同样也应该撤销当前元素（这说明包含有当前节点的路径都已经全部走完）

